package leetcode.array;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author Cheng Jun
 * Description: 给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，
 * 请你判断一个人是否能够参加这里面的全部会议。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/meeting-rooms
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2022/1/7 13:32
 * <p>
 * 0 <= intervals.length <= 10^4
 * intervals[i].length == 2
 * 0 <= starti < endi <= 10^6
 */
public class canAttendMeetings {

    // 输入：intervals = [[0,30],[5,10],[15,20]]
    // 输出：false
    // 我想到一个 好办法，利用 优先队列
    public boolean canAttendMeetings(int[][] intervals) {
        int length = intervals.length;
        // 数组为空
        if (length == 0) {
            return true;
        }
        // 按照 开始时间排序
        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));
        for (int i = 0; i < length - 1; i++) {
            // 区间重叠
            if (intervals[i][1] > intervals[i + 1][0]) {
                return false;
            }
        }
        return true;
    }

    // 利用 优先队列
    public boolean canAttendMeetings1(int[][] intervals) {
        // 数组为空
        if (intervals.length == 0) {
            return true;
        }
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(interval -> interval[0]));
        for (int[] interval : intervals) {
            priorityQueue.add(interval);
        }
        int endTime = -1;
        while (!priorityQueue.isEmpty()) {
            int[] interval = priorityQueue.poll();
            if (interval[0] >= endTime) {
                endTime = interval[1];
            } else {
                return false;
            }
        }
        return true;
    }
}
